package at.tasat.solver;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;

import at.tasat.util.IntKeyMap;
import at.tasat.util.IntList;

public abstract class Queue implements Iterable<Integer>, Cloneable {
	private final IntList queue;
	private final IntKeyMap<IntList.Node> nodes;

	public Queue(int numVariables) {
		queue = new IntList();
		nodes = new IntKeyMap<IntList.Node>(1, numVariables);
	}

	public final int size() {
		return nodes.size();
	}

	public final boolean contains(int variableId) {
		return nodes.containsKey(variableId);
	}

	public final int peek() {
		assert size() > 0;
		return queue.get(0).getValue();
	}

	public final Integer dequeue() {
		assert size() > 0;
		int variableId = peek();
		nodes.remove(variableId);
		queue.remove(0);
		return variableId;
	}

	public final void enqueue(int variableId) {
		insert(getIndexForEnqueue(variableId), variableId, true);
	}

	protected abstract int getIndexForEnqueue(int variableId);

	public final void reenqueue(int variableId) {
		insert(getIndexForReenqueue(variableId), variableId, true);
	}

	protected abstract int getIndexForReenqueue(int variableId);

	private void insert(int index, int variableId, boolean fireOnAdded) {
		assert !contains(variableId);
		IntList.Node node = queue.add(index, variableId);
		nodes.put(variableId, node);
		if (fireOnAdded) {
			onAdded();
		}
	}

	protected void onAdded() {
		// nothing to do
	}

	public final void remove(int variableId) {
		assert contains(variableId);
		IntList.Node node = nodes.get(variableId);
		queue.remove(node);
		nodes.remove(variableId);
		onRemoved();
	}

	protected void onRemoved() {
		// nothing to do
	}

	protected void sort(Comparator<Integer> comparator) {
		Integer[] array = toArray();
		Arrays.sort(array, comparator);
		queue.clear();
		nodes.clear();
		for (int i = 0; i < array.length; i++) {
			insert(i, array[i].intValue(), false);
		}
	}

	@Override
	public Iterator<Integer> iterator() {
		return queue.iterator();
	}

	public Integer[] toArray() {
		Integer[] array = new Integer[size()];
		Iterator<Integer> iterator = iterator();
		int index = 0;
		while (iterator.hasNext()) {
			array[index++] = iterator.next();
		}
		return array;
	}

	public void copy(Queue to) {
		assert (to.size() == 0);
		int i = 0;
		for (Integer variableId : this) {
			to.insert(i++, variableId, false);
		}
	}

	public int getNumVariables() {
		return nodes.getMaximalValue();
	}

	@Override
	public String toString() {
		return Arrays.toString(toArray());
	}
}
